package leetcode_141_160;

import utils.ListNode;


public class insertionSortList_147 {
    /**
     * 使用 插入排序 对链表进行排序
     * @return 返回 排序后链表的头 。
     */
    public ListNode insertionSortList(ListNode head) {
        /**
         * 思路是从前往后遍历
         * 维护一个有序链表，front,tail作为这个有序链表的头尾指针
         * 将后续每一个节点插入进该链表
         * 2ms
         */
        tail=head;
        front=head;
        ListNode root=head.next;
        while (root!=null){
            ListNode nextRoot=root.next;//对循环内的操作不能影响循环的次序
            if(root.val<=front.val){     ////如果小于等于头指针，直接放在最后边即可
                root.next=front;
                front=root;
            } else if(root.val>=tail.val){    //如果大于等于尾指针，直接放在最后边即可
                tail.next=root;
                tail=root;
            }else
                embedNode(front,root); //否则插入
            root=nextRoot;
        }
        tail.next=null;
        return front;
    }
    ListNode tail;   //尾指针
    ListNode front;  //头指针

    void embedNode(ListNode front,ListNode node){
        ListNode root=front;
        while (root!=null){
            ListNode nextRoot=root.next;//对循环内的操作不能影响循环的次序

            if(node.val >=root.val && node.val<root.next.val ) {    //如果大于等于当前节点又小于后边一个节点，插入
                node.next=root.next;
                root.next=node;
                return;
            }

            if(root==tail)
                return;
            root=nextRoot;
        }
    }
}
